package com.zwj.interview.完全二叉树;

/**
 * @Author: Zwj
 * @Date: 2022/2/27 18:29
 */
public class BST中删除一个数 {

    //删除值等于key的节点
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (root.val == key) {
            //如果要删除的节点没有左右子节点，或者左右节点只有其一，那么直接返回其一个子节点
            //下面两种情况就是只有一个节点的情路
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            //当要删除的节点有左右子节点时，此时就需要找到该节点的右子树中最小的节点minNode，
            // 然后使用该节点的值替换要删除的节点，最后再删除替换后的节点minNode
            // 必须找到左⼦树中最⼤的那个节点，或者右⼦树中最⼩的那个节点来接替⾃⼰
            TreeNode minNode = getMin(root.right);
            root.val = minNode.val;
            //删除最小的那个节点，这个节点是root的右节点
            root.right = deleteNode(root.right, minNode.val);
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }





    private TreeNode getMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}